package algorithm;

/**
 * @author rongkai
 * @description: 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ **注意：**给定 n 是一个正整数。
 * @date 2021/3/8
 */
public class Solution15 {

    public static void main(String[] args) {
        int n = 4;
        System.out.println(solution(n));
    }

    /**
     * DP问题，归纳总结出dp(n) = dp(n-1)+dp(n-2)
     * @param n
     * @return
     */
    public static int solution(int n){
        if (n == 1){
            return 1;
        }
        if (n == 2){
            return 2;
        }
        int first = 1;
        int second = 2;
        for (int i = 3; i <= n; i++) {
            int temp = first+second;
            first = second;
            second = temp;
        }
        return second;
    }
}
